package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/7/15.<br><br>
 *
 * 排列硬币
 */
public class Topic441 {

    public static void main(String[] args) {
        Topic441 instance = new Topic441();

        System.out.println(instance.arrangeCoins(1));
        System.out.println(instance.arrangeCoins(2));
        System.out.println(instance.arrangeCoins(5));
        System.out.println(instance.arrangeCoins(6));
        System.out.println(instance.arrangeCoins(8));
        System.out.println(instance.arrangeCoins(2147483647));
    }

    public int arrangeCoins(int n) {
        int row = 0;

        int low = 1;
        int high = n;
        while (low <= high) {
            int mild = low + (high - low) / 2;
            long mul = ((long) mild * (mild + 1)) / 2;
            if(mul > n) {
                high = mild - 1;
            }
            else if(mul <= n) {
                row = mild;
                low = mild + 1;
            }
        }

        return row;
    }

    public int arrangeCoins2(int n) {
        int floor = 1;
        long counter = 1;

        while (counter <= n) {
            counter += ++floor;
        }

        return floor - 1;
    }
}
